#define  _CRT_SECURE_NO_WARNINGS
class Solution {
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int i = left, j = mid + 1, cur = left;
        while (i <= mid && j <= right)
        {
            if (nums[i] <= nums[j])
                // if(nums[i] > nums[j])
            {
                // count += right - j + 1;
                tmp[cur++] = nums[i++];
            }
            else
            {
                tmp[cur++] = nums[j++];
                count += mid - i + 1;
            }
        }
        while (i <= mid) tmp[cur++] = nums[i++];
        while (j <= right) tmp[cur++] = nums[j++];
        for (int i = left; i <= right; i++) nums[i] = tmp[i];
    }
    vector<int> tmp;
    int count = 0;
public:
    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        mergeSort(record, 0, record.size() - 1);
        return count;
    }
};